<?php

//判断链表是否有环
class LinkedListIsCycle {

    /**
     * 判断是否有环
     * @param Node $head
     * @return bool
     */
    private function isCycle(Node $head) {
        //p1每次走1步, p2每次走2步, 如果相遇则有环

        $p1 = $head;
        $p2 = $head;
        while ($p2 !== null && $p2->next !== null) {
            $p1 = $p1->next;
            $p2 = $p2->next->next;//每次走两步
            if ($p1 === $p2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 计算环的长度
     * @param Node $head
     * @return int
     */
    private function calcCycleLength(Node $head) {
        //p1每次走1步, p2每次走2步, 从第1次相遇后开始计算到第2次相遇时p1的步数

        $meetTimes = 0;//第几次相遇
        $steps = 0;//走了多少步

        $p1 = $head;
        $p2 = $head;
        while ($p2 !== null && $p2->next !== null) {
            $p1 = $p1->next;
            $p2 = $p2->next->next;//每次走两步
            if ($p1 === $p2) {
                $meetTimes++;
                if ($meetTimes == 1) {
                    //从第一次相遇开始计算步数
                    $steps = 0;
                } else if ($meetTimes == 2) {
                    //第二次相遇
                    return $steps;
                }
            }
            $steps++;
        }

        return $steps;
    }

    /**
     * 计算入环点
     * @param Node $head
     * @return Node
     */
    public function calcCycleEntrance(Node $head) {
        //把p1放到头节点位置, 把p2放到首次相遇点, 则当他们以相同的速度再次相遇时, 就是入环节点

        //p1每次走1步, p2每次走2步, 从第1次相遇
        $p1 = $head;
        $p2 = $head;
        while ($p2 !== null && $p2->next !== null) {
            $p1 = $p1->next;
            $p2 = $p2->next->next;//每次走两步
            if ($p1 === $p2) {
                //首次相遇点
                break;
            }
        }

        //把p1放到头节点位置, p2不动(在第一次相遇点), 然后以相同的速度前进
        $p1 = $head;
        while ($p2 !== null && $p2->next !== null) {
            //以相同的速度前进
            $p1 = $p1->next;
            $p2 = $p2->next;
            if ($p1 === $p2) {
                //首次相遇点
                break;
            }
        }
        return $p1;
    }

    public function __construct() {
        //               1 <- 8
        //               ↓    ↑
        //5 -> 3 -> 7 -> 2 -> 6

        $node1 = new Node(5);
        $node2 = new Node(3);
        $node3 = new Node(7);
        $node4 = new Node(2);
        $node5 = new Node(6);
        $node6 = new Node(8);
        $node7 = new Node(1);
        $node1->next = $node2;
        $node2->next = $node3;
        $node3->next = $node4;
        $node4->next = $node5;
        $node5->next = $node6;
        $node6->next = $node7;
        $node7->next = $node4;
        if ($this->isCycle($node1)) {
            echo 'has cycle: Yes' . PHP_EOL;
            echo 'cycle length: ' . $this->calcCycleLength($node1) . PHP_EOL;
            echo 'cycle entrance: ' . PHP_EOL;
            var_dump($this->calcCycleEntrance($node1));
        } else {
            echo 'has Cycle: No' . PHP_EOL;
        }
    }

}

class Node {

    public string $data;
    //public Node $next;//这里不能指定类型为Node, 否则php7.4不接受null类型
    public $next;

    /**
     * @param string $data
     * @param Node $next
     */
    public function __construct(string $data = null, Node $next = null) {
        $this->data = $data;
        $this->next = $next;
    }

}

$m = new LinkedListIsCycle();

